Three-dimensional (3D) objects are commonly represented in computer graphics applications as an approximation of their surface via a sufficiently large number of polygons, such as triangles. Graphical output devices for displaying computer graphics are typically raster devices having a display area or screen comprised of a set of discrete picture elements referred to as pixels as illustrated in FIG. 1. Each pixel on the screen is associated with one entry in a display buffer (also referred to as a "frame buffer") which stores a value for the color of each pixel. The frame buffer is then loaded with image information and that information is displayed by the pixels of the display.
The approximation of a cylindrical surface using multiple triangles may be used to illustrate the use of polygons to approximate an object. The steps for approximating the surface of a cylindric object via multiple triangles (also referred to as "primitives") are illustrated in FIG. 2. For display purposes, each triangle is typically decomposed into a set of screen pixels, a process called "rasterization". Rasterization is usually implemented via a specific rasterizer chip.
Referring now to FIG. 3, a conventional layout of graphics system hardware is schematically illustrated. As seen in FIG. 3, an application program 1 may display a 3D graphic object (image) on a conventional two-dimensional (2D) display 2. Typically, the 3D data is stored in a database 3. A processing unit (CPU) 4 may control the 3D data input to the database 3 and a geometric graphics unit 5 which is responsible for geometric object transformations like scaling, moving or rotating the objects. The CPU 4 may also control a rasterizer 7 for decomposing each primitive into pixels. A pixel driver 8, which is also connected to the CPU 4, controls the display 2 for 2D presentation of 3D graphics.
In converting from a 3D representation of an image to a 2D representation, the visible parts of an object can be determined by computing for each pixel a measure of the distance to the observer, called Depth Value or "Z-Value", and by comparing that Z-Value to the Z-Value of the pixel previously generated for a particular screen address. Routines for handling visible surface determination within 3D graphics display systems are known. The most common of these routines relate to pre-sorting of objects/polygons according to depth before rasterization, or relate to depth buffering.
A depth sort routine, developed by Newell and Sancha (Newel, M. E., R. G. Newell, and T. L Sancha, "A solution to the Hidden Surface Problem", in Proceedings of the ACM National Conference 1972, 433-450), paints polygons into a frame buffer in order of decreasing distance from the viewpoint. Three conceptual steps are performed: 1) sorting all polygons according to the smallest (farthest) Z coordinate of each; 2) resolving any ambiguities resulting when Z coordinates of polygons overlap, and splitting polygons if necessary; and 3) scan-converting each polygon in ascending order of smallest Z coordinate, (i.e. from back to front).
For CPU performance reasons, pre-sorting of polygons is used typically for smaller scenes having a relatively small number of objects. Other routines may be used for applications dealing with more complex 3D) scenes. As used herein, the term "scene" is synonymous with the terms "graphics" and "images".
The depth-buffer routine, developed by E. Catmull, and disclosed in an article entitled "A Subdivision Algorithm for Computer Display of Curved Surfaces" (published in Ph.D. Thesis, Computer Science Department, University of Utah, December 1974), is commonly implemented in 3D display system. This routine requires a frame buffer in which color values are stored, and a Z-Buffer, with the same number of entries, in which a Z-Value (depth value) is stored for each pixel of a scene, as illustrated in FIG. 5A. The Z-Buffer is initialized to zero, representing the Z-Value at the back clipping plane. The frame buffer is initialized to the background color. The largest value that can be stored in the Z-Buffer represents the Z-Value (or depth) of the front clipping plane. The advantage of this routine is that polygons which belong to any object can be rendered in arbitrary order independent of their depth. However, depth buffer routines may require large amounts of memory, which is less of a significant disadvantage as semiconductor memory increases in density which decreases cost.
In a depth-buffer routine, during the scan conversion process, if the polygon point being scan-converted at (X, Y) is no farther from the viewer than is the point whose color and depth are currently in the frame buffer and the Z-Buffer, respectively, then the color and depth of the new points replace the old values, as illustrated in FIG. 5B. Prior art implementations of depth buffer routines typically have a dedicated Z-Buffer integrated in dynamic random access memory (DRAM). The rasterizer typically requires at least one access to the Z-Buffer and one comparison of the old and new depth values. Around 50% of the pixels typically require write access to the external Z-Buffer. The operations and accesses typically are done at pixel frequency. Limiting factors for a Z-Buffer routine include: the access time to the dedicated DRAM Z-Buffer; overall bandwidth requirements during Z-Buffer access; and cost of on-board space for the dedicated Z-Buffer memory.
In U.S. Pat. No. 4,475,104 a method of generating a two-dimensional image representing a three-dimensional image or scene in the form of an array of pixels utilizes "depth buffer" or "Z-Buffer" hidden surface removal (HSR) is provided. The hidden surface removal occurs at the time of scan conversion and attempts to ensure that the image of an object in the scene, which has already been converted, is not overwritten by input pixel data which arrives later, but in fact, corresponds to an object behind the one already stored. In the depth-buffer routine, the stored foreground color is overwritten if the input depth is less than the stored foreground depth. The input depth is then stored as a new foreground depth.
The depth-buffer routine is described more generally in "Principles of Interactive Computer Graphics", page 369, by W. M. Newman and R. F. Sproull. As described by Newman and Sproull, the routine does not require knowledge of any object other than that being scan-converted at the time.
Referring now to FIG. 4, a conventional three-dimensional graphic display apparatus is schematically illustrated. A line generator generates X-, Y-, and Z-coordinate data in a three-dimensional coordinate system. The output of the line generator is fed into a depth-buffer memory 10 which stores coordinate data representing the depth of each pixel in order to execute a hidden-surface process of a graphic image on the basis of the X-, Y-, and Z-data supplied from the line generator. X- and Y-coordinate data from the line generator and the Z-coordinate data from the depth-buffer memory 10 are input into a frame buffer memory 11. The frame buffer memory 11 stores display information used to display an image on the basis of the data feed from the line generator and the depth-buffer memory 10. The output of the frame buffer memory 11 is delivered to a cathode ray tube (CRT) 12 which displays the three-dimensional scene.
Since the depth-buffer routine needs a depth-buffer memory with a large capacity of storage, a DRAM is usually used because of its relatively low cost. Unfortunately, DRAMs typically have a slow access speed. In a hidden-surface process, a depth-buffer memory operates to read out depth information (Z-coordinate data), to compare this information, and to update this depth information. Consequently, the depth-buffer memory is required to execute a READ-WRITE cycle, which often results in slow operating speeds as compared with the line generator and the frame buffer memory operating in synchronism with the depth-buffer memory. As a result, it is often difficult to achieve higher hidden-surface processing speeds in a conventional three-dimensional graphics display system.
One approach to addressing memory bandwidth problems caused by the Z-Buffer bottleneck is disclosed in an article by G. Knittel and A. Schilling, University of Tubingen, Germany, (related to the MONOGRAPH project, and supported by the European CEC's ESPRIT programme). Presented therein is a memory design which integrates the required compare logic into the Z-Buffer memory devices, and performs the complete Z-Buffer routine on a chip. This method is advantageous because internal bandwidth becomes available, and the read-modify-write cycles are turned into merely write cycles from an external point of view.
Another approach to the bandwidth problem is disclosed in European Patent Application 0,500,035, where a 3D graphics display system is provided with a modified depth-buffer routine. In the modified depth-buffer routine READ-WRITE cycles are performed in a depth buffer memory only when patterns are actually overlapped and when Z coordinate data has to be compared with each other. Because it is not necessary to compare z coordinate data, only WRITE cycles are performed in the depth-buffer memory if the patterns are not overlapped. As a result, the hidden-surface process executed in a three-dimensional graphic display system has increased speed.
Another method of hidden-surface processing is disclosed in Japanese Patent Public Disclosure No. 42279/1987 (published on Feb. 24, 1987) and claims increased efficiency in the depth information comparison. As described in the Disclosure No. 42279/1987, with respect to the depth information comparison process, a Z-Value is updated on the basis of an "AND" condition. Such a process may be complicated and may not be suited for a hidden-surface process in a depth-buffer routine.
As is clear from the discussion above, the rendering of three-dimensional graphic images on a two-dimensional raster scan display screen often involves the use of a frame buffer to store the final image. The information in the frame buffer is often the end product of numerous data manipulations involving the generation of three-dimensional objects by a processor. Depth comparisons referenced to a Z-Buffer may be used to render into the frame buffer only the objects or portions thereof which are visible. The frame buffer memory is a special purpose type of memory in which the memory locations correspond to locations, or pixels, on a monitor, or other type of display. Known graphics systems may not provide for efficient use of a main memory, because information is transferred between the main memory and the frame buffer memory via a system bus under control of a CPU. Therefore, known computer graphics systems have a CPU cache memory which contains the information in memory locations most frequently accessed by the CPU.
A typical cache memory system consists of cache random access memory (RAM), a cache controller, is and a tag store. The tag store is a table of the main memory addresses of the information that is stored in the cache RAM. The cache RAM stores the information that is operated on by the CPU. The cache controller controls the information that passes in and out of the cache RAM, and updates the cache tag store. The specific structure of the cache tag store and its entries are dependent on whether a cache is a direct mapped cache, a set associative cache, or a fully associative cache. One characteristic of all cache tag stores, however, is that they need a method for indicating the main memory addresses corresponding to the entries in the cache memory. When the CPU needs the information in a main memory address, the tag store is searched for the main memory address. If the main memory address is in the tag store (a cache "hit"), the information is retrieved from the cache RAM and sent to the CPU. If the main memory address is not in the tag store (a cache "miss"), the cache controller retrieves the information from the main memory, stores it in the cache RAM, and records the main memory address in the tag store. When the CPU stores the information, it sends the information back to the cache controller which stores the information in the cache RAM. If the cache is a "write through" cache, the information is also written to the corresponding address in the main memory. If the cache is a "write back" cache, the information is not written to the corresponding address in the main memory until a later time.
Several attempts have been made to utilize a cache in graphics processing. One such approach is seen in International Patent Application WO95/24682 which describes a semiconductor chip in a computer graphics display system for performing texture mapping. A cache memory is used to accelerate the reading and writing of texture elements ("texels"). In texture mapping, a pattern image or texture map is combined with an area or surface of an object to produce a modified object with the added detail of the texture map. As the surface of an object is rendered, the respective two-dimensional index data necessary for associating two-dimensional information into an array of texture pixels are interpolated and used to look-up a texture value for each rendered pixel. The computer graphics systems described in Application WO95/24682 require a fast, accurate and efficient texture mapping process. The texture maps are stored in a main memory. The data for recent texture maps are cached in order to accelerate the reading and writing of texels. When a DRAM row is accessed, its contents can be transferred to the cache while simultaneously accessing the cache and cycling the DRAM array again. The memory access cycles can be performed in parallel due to reading from the cache. Further, a graphics subsystem is provided for processing object data into a screen coordinate system. The subsystem generates pixel data based on primitives (e.g., points, lines, polygons, and meshes) from the subsystem. The pixel data is sent to another subsystem, whereupon Z-Buffering, blending, texturing, and anti-aliasing functions are performed. The resulting pixel values are stored in a frame buffer. The cache memory coupled to the main memory is used for storing recently used texture data.
Another method and system for caching graphic S information for display in a graphics processing system is described in International Patent Application WO95/16960. The described system and method may avoid repeated rendering each time a graphic is required to be redrawn. The method and system described therein are directed to specifying which graphic objects should be cached and requesting that caching be carried out for those graphics. The proposed caching system is performed explicitly at the request of a developer. A cached graphic image may be stored in a device-dependent manner so that the cached image can be transferred directly to the respective device with little or no interpretation such as scaling, bit-depth translation, color look-up, and the like.
The various approaches described above, in particular the cache approaches, are typically insufficient for use with the a Z-Buffer routine, which is usually implemented in 3D hardware accelerators for visible surface determination. Consequently, disadvantages in performance and cost with respect to visible surface determination typically exist in graphics display systems.